public class ReorderList {
    // leetcode 重排链表
    // https://leetcode.cn/problems/reorder-list/description/
    public void reorderList(ListNode head) {
        // 将链表分为两个部分，前半部分和后半部分，然后将后半部分的链表进行逆序，然后合并两个链表
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode head2 = reverseList(slow);
        mergeList(head, head2);
    }

    private void mergeList(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) return;
        ListNode cur1 = head1, cur2 = head2;
        while (cur1 != null && cur2 != null) {
            ListNode nextCur1 = cur1.next, nextCur2 = cur2.next;
            cur1.next = cur2;
            if (nextCur1 != null) {
                cur2.next = nextCur1;
            }
            cur1 = nextCur1;
            cur2 = nextCur2;
        }
    }

    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode nextCur = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextCur;
        }
        return prev;
    }
}
